Cream of the Crop 12/Cream of the Crop 12 (Part II)/Cream of the Crop 12 (Part II).iso/OS2/GNUSED.ZIP/rx/rxbitset.c

C/C++ Source or Header | 1995-12-31 | 6.7 KB | 371 lines

/***********************************************************

Copyright 1995 by Tom Lord

                        All Rights Reserved

Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in
supporting documentation, and that the name of the copyright holder not be
used in advertising or publicity pertaining to distribution of the
software without specific, written prior permission.

Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
PERFORMANCE OF THIS SOFTWARE.

******************************************************************/


/*
 * Tom Lord ([e-mail], [e-mail])
 */


#include "rxall.h"
#include "rxbitset.h"


#ifdef __STDC__
int
rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b)
#else
int
rx_bitset_is_equal (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  RX_subset s;

  if (size == 0)
    return 1;

  s = b[0];
  b[0] = ~a[0];

  for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x)
    ;

  b[0] = s;
  return !x && (s == a[0]);
}


#ifdef __STDC__
int
rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b)
#else
int
rx_bitset_is_subset (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  x = rx_bitset_numb_subsets(size) - 1;
  while (x-- && ((a[x] & b[x]) == a[x]));
  return x == -1;
}


#ifdef __STDC__
int
rx_bitset_empty (int size, rx_Bitset set)
#else
int
rx_bitset_empty (size, set)
     int size;
     rx_Bitset set;
#endif
{
  int x;
  RX_subset s;
  s = set[0];
  set[0] = 1;
  for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
    ;
  set[0] = s;
  return !s;
}

#ifdef __STDC__
void
rx_bitset_null (int size, rx_Bitset b)
#else
void
rx_bitset_null (size, b)
     int size;
     rx_Bitset b;
#endif
{
  bzero (b, rx_sizeof_bitset(size));
}


#ifdef __STDC__
void
rx_bitset_universe (int size, rx_Bitset b)
#else
void
rx_bitset_universe (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x = rx_bitset_numb_subsets (size);
  while (x--)
    *b++ = ~(RX_subset)0;
}


#ifdef __STDC__
void
rx_bitset_complement (int size, rx_Bitset b)
#else
void
rx_bitset_complement (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x = rx_bitset_numb_subsets (size);
  while (x--)
    {
      *b = ~*b;
      ++b;
    }
}


#ifdef __STDC__
void
rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_assign (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] = b[x];
}


#ifdef __STDC__
void
rx_bitset_union (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_union (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] |= b[x];
}


#ifdef __STDC__
void
rx_bitset_intersection (int size,
            rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_intersection (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] &= b[x];
}


#ifdef __STDC__
void
rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_difference (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] &=  ~ b[x];
}


#ifdef __STDC__
void
rx_bitset_revdifference (int size,
             rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_revdifference (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] = ~a[x] & b[x];
}

#ifdef __STDC__
void
rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_xor (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] ^= b[x];
}


#ifdef __STDC__
unsigned long
rx_bitset_hash (int size, rx_Bitset b)
#else
unsigned long
rx_bitset_hash (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x;
  unsigned long answer;

  answer = 0;

  for (x = 0; x < size; ++x)
    {
      if (RX_bitset_member (b, x))
    answer += (answer << 3) + x;
    }
  return answer;
}


RX_subset rx_subset_singletons [RX_subset_bits] =
{
  0x1,
  0x2,
  0x4,
  0x8,
  0x10,
  0x20,
  0x40,
  0x80,
  0x100,
  0x200,
  0x400,
  0x800,
  0x1000,
  0x2000,
  0x4000,
  0x8000,
  0x10000,
  0x20000,
  0x40000,
  0x80000,
  0x100000,
  0x200000,
  0x400000,
  0x800000,
  0x1000000,
  0x2000000,
  0x4000000,
  0x8000000,
  0x10000000,
  0x20000000,
  0x40000000,
  0x80000000
};


/*
 * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l)))))
 * (define lb (map (lambda (n) (number->string n 2)) l))
 * (define lc (map string->list lb))
 * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc))
 * (define lt (map (lambda (l) (apply + l)) ln))
 */

static int char_pops[256] =
{
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

#define RX_char_population(C) (char_pops[C])

#ifdef __STDC__
int
rx_bitset_population (int size, rx_Bitset a)
#else
int
rx_bitset_population (size, a)
     int size;
     rx_Bitset a;
#endif
{
  int x;
  int total;
  unsigned char s;

  if (size == 0)
    return 0;

  total = 0;
  x = sizeof (RX_subset) * rx_bitset_numb_subsets(size) - 1;
  while (x >= 0)
    {
      s = ((unsigned char *)a)[x];
      --x;
      total = total + RX_char_population (s);
    }
  return total;
}